from typing import Optional

from BuildTree import TreeNode, build_tree_from_level_order


class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        # 第一步找到节点的位置
        if not root: return None
        if root.val == key:
            if not root.left and not root.right: return None
            if not root.left and root.right: return root.right
            if root.left and not root.right: return root.left
            curr = root.right
            while curr.left:
                curr = curr.left
            curr.left = root.left
            return root.right
        elif root.val < key:
            return self.deleteNode(root.right, key)
        else:
            return self.deleteNode(root.left, key)


if __name__ == '__main__':
    s = Solution()
    null = None
    rot = build_tree_from_level_order([3])
    r = s.deleteNode(rot, 3)
    print()
